package LeetCode.month04.day118;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 16778
 * @date 2025/11/28 10:45
 * @description
 */
public class No2872 {
    private int ans;

    public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, _ -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            g[x].add(y);
            g[y].add(x);
        }

        dfs(0, -1, g, values, k);
        return ans;
    }

    // 返回子树 x 的点权和
    private long dfs(int x, int fa, List<Integer>[] g, int[] values, int k) {
        long sum = values[x];
        for (int y : g[x]) {
            if (y != fa) { // 避免访问父节点
                // 加上子树 y 的点权和，得到子树 x 的点权和
                sum += dfs(y, x, g, values, k);
            }
        }
        ans += sum % k == 0 ? 1 : 0;
        return sum;
    }
}
